package leetcode.code0030;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution extends Solution30 {

	@Override
	public List<Integer> findSubstring(String s, String[] words) {
		Map<String, Integer> wordsMap = new HashMap<>();
		for (String word : words) {// 单词表
			Integer num = wordsMap.getOrDefault(word, 0) + 1;
			wordsMap.put(word, num);
		}
		int size = words.length;// 单词表个数
		int wordLen = words[0].length();// 每个单词长度
		int total = wordLen * size;// 单词表总长度, s至少要这么长才有可能是
		List<Integer> ans = new ArrayList<>();
		if (s.length() < total) { // 小于就不可能是
			return ans;// 这里不能返回null ... 坑1
		}
		char[] str = s.toCharArray();
		int strLen = s.length();
		for (int i = 0; i < strLen && i + total <= strLen; i++) {// i + total <= strLen 限制最后的起始位置,不足量的不看了
			String part = new String(str, i, wordLen);// 每一个起始点开始,wordLen的字符串
			Integer num = wordsMap.getOrDefault(part, 0);// 在单词表内的数量
			if (num != 0) {// 说明从i开始的长度wordLen字符串,是目标中一个
				// 看看从i开始total长的字符串是不是都是
				boolean has = this.f(str, i, new HashMap<>(wordsMap), wordLen, size, total);
				if (has) {
					ans.add(i);
				}
			}
		}
		return ans;
	}

	private boolean f(char[] str, int i, HashMap<String, Integer> hashMap, int wordLen, int size, int total) {
		if (str.length - i + 1 < total) {// 长度不够
			return false;
		}
		for (int j = i; j < i + total && j + wordLen <= i + total; j = j + wordLen) {
			String part = new String(str, j, wordLen);
			Integer num = hashMap.getOrDefault(part, 0);
			if (num == 0)
				return false;// 单词表中没有了,这段肯定不是
			else
				hashMap.put(part, num - 1);// 消除一个单词
		}
		return true;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug5();
		so.debug4();
		so.debug1();
		so.debug2();
		so.debug3();
	}

}
